package com.example.tree;

/**
 * Created by Quincy on 2018/9/12.
 *
 * 输入两棵二叉树A，B，判断B是不是A的子结构
 （ps：我们约定空树不是任意一个树的子结构）

 首先从根节点开始遍历
 再分别从左子树和右子树遍历来判断B是不是A的子结构
 */
public class SubTreeNode {
    public class TreeNode{
        int val;
        TreeNode left = null;
        TreeNode right = null;
        TreeNode(int val){
            this.val = val;
        }
    }

    public static boolean hasSubTree(TreeNode root1, TreeNode root2){
        boolean result = false;
        //当两棵树不为空
        if (root1 != null && root2 != null){
            if (root1.val == root2.val){
                //从根节点开始比较
                result = doesTree1HaveTree2(root1,root2);
            }
            if (!result){
                //如果根节点不符合，从左子树开始比较
                result = hasSubTree(root1.left, root2);
            }
            if (!result){
                //如果左子树不符合，从右子树开始比较
                result = hasSubTree(root1.right, root2);
            }
        }
        return result;
    }

    private static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
        if (node2 == null){
            return true; //若B与A的子树相等就返回true
        }
        if (node1 == null){//若B还没遍历完，A就遍历完了，表示false
            return false;
        }
        if (node1.val != node2.val){//若两颗树在比较时，有一个节点不相等，则返回false
            return false;
        }
        return doesTree1HaveTree2(node1.left, node2.left)&&doesTree1HaveTree2(node1.right, node2.right);
    }
}
